package zuochengyun.chapter9;

import java.util.Arrays;

//在旋转数组中查找指定的数
public class SearchInRotatedSortArray {

	public static void main(String[] args) {
		SearchInRotatedSortArray object = new SearchInRotatedSortArray();
		int[] arr = {0,2,2,3,5,0,0,0,0,0};
		int[] arr1 = {0,0,0,1,0};
		int[] arr2 = {0,1,0,0,0};
		int[] arr3 = {3,6, 8, 10, 2, 3};
		int[] arr4 = {3,9, 0, 1, 2, 3};
		System.out.println(object.search(arr, 1));
		System.out.println(object.search(arr1, 1));
		System.out.println(object.search(arr2, 1));
		System.out.println(object.search(arr3, 5));
		System.out.println(object.search(arr4, 4));
	}
	
	
	//该数组可能会存在重复的数
	public boolean search(int[] nums, int target) {
        if(nums == null || nums.length <= 0){
            return false;
        }
        //首先需要找到分界点
        //如果恰好旋转回到了原使状态
        int boundary = 0;	//boundary指向最小的元素下标
        if(nums[0] <  nums[nums.length - 1] || nums.length == 1){
            return binarySearch(nums, 0, nums.length - 1, target) != -1;
        }else{
            boundary = getMinIndex(nums);
        }
        
        //重构排好序的数组
        System.out.println(" boundary: " + boundary);
        int[] left = Arrays.copyOfRange(nums, 0, boundary);
        for (int i = 0; i < left.length; i++) {
			System.out.print(left[i] + " ");
		}
        System.out.println();
//        System.out.println("right array is: ");
        int[] right = Arrays.copyOfRange(nums, boundary, nums.length);
        for (int i = 0; i < right.length; i++) {
			System.out.print(right[i] + " ");
		}
        System.out.println();
        int index = -1;
        if( (index = binarySearch(left, 0, left.length - 1, target)) != -1){
        	return true;
        }else{
        	index = binarySearch(right, 0, right.length - 1, target);
        }
        return index != -1;
    }
	
	//获取到断点的下标
	public int getMinIndex(int[] arr){
		int low = 0;
		int high = arr.length - 1;
		int mid = 0;
		//由于这个二分的时候不是mid - 1， mid + 1,所以如果low = high - 1的时候mid会等于low
		//会造成死循环的出现，所以我们此时就退出了，在返回的时候进行判断即可
		while(low < high){
			if(low == high - 1){
				break;
			}
			if(arr[low] < arr[high]){
				return arr[low];
			}
			mid = (high + low) / 2;
			if(arr[low] > arr[mid]){
				high = mid;
				continue;
			}
			if(arr[mid] > arr[high]){
				low = mid;
				continue;
			}
			//如果以上情况都不符合，说明arr[low] >= arr[high], arr[low] <= arr[mid], arr[mid] <= arr[high]
			//所以只有arr[low] == arr[mid] == arr[high]
			//此时仍然可以使用二分法
			while(low < mid){
				if(arr[low] == arr[mid]){
					low++;
				}else if(arr[low] < arr[mid]){
					return arr[low];
				}else{
					high = mid;
					break;
				}
			}
		}
		if(arr[high] < arr[low]){
			return high;
		}else{
			return low;
		}
	}
	
	public int binarySearch(int[] nums, int left, int right, int target) {
		int middle = left + (right - left) / 2;
		while (left <= right) {
			middle = left + (right - left) / 2;
//			System.out.println("left: " + left + " right: " + right);
			if (nums[middle] == target) {
				return middle;
			} else if (nums[middle] < target) {
				left = middle + 1;
			} else {
				right = middle - 1;
			}
		}
		return -1;
	}
}
